class Solution
{
public:
    string addBinary(string a, string b)
    {
        int top = 0;
        string ans;
        int ed1 = a.size() - 1, ed2 = b.size() - 1;
        ans.resize(max(ed1, ed2) + 1);
        int k = ans.size() - 1;
        while (ed2 >= 0 || ed1 >= 0)
        {
            int t = top;
            if (ed1 >= 0)
                t += a[ed1] - '0', --ed1;
            if (ed2 >= 0)
                t += b[ed2] - '0', --ed2;
            // cout << t << endl;
            top = t / 2;
            ans[k--] = t % 2 + '0';
        }
        if (top)
            return '1' + ans;
        else
            return ans;
    }
};